package basic.study.algorithms.solution.DynamicProgramming;

import java.util.HashMap;

/**
 * @author Kevin
 * @date 2020/2/19 15:21
 * 1 元、3 元、5 元，我们要支付 9 元，最少需要 3 个硬币（3 个 3 元的硬币）
 */
public class minCoins {
    //动态规划-状态转移方程法
    private static HashMap<Integer, Integer> hashMap = new HashMap<>();

    public static void main(String[] args) {
        hashMap.put(0,0);
        hashMap.put(1,1);
        hashMap.put(2,2);
        hashMap.put(3,1);
        hashMap.put(4,2);
        hashMap.put(5,1);
        System.out.println(exchange(9));

        System.out.println(exchange1(9, new int[9+1]));
    }

    public static int exchange(int money) {
        if (hashMap.get(money) != null) return hashMap.get(money);
        int times = 1 + Math.min(Math.min(exchange(money-1), exchange(money-3)), exchange(money-5));
        hashMap.put(money, times);
        return times;
    }

    //动态规划-状态转移表法
    public static int exchange1(int money,int[] states) {
        states[0] = 0;
        states[1] = 1;
        states[2] = 2;
        states[3] = 1;
        states[4] = 2;
        states[5] = 1;
        if (states[money] != 0) return states[money];
        int times = 1 + Math.min(Math.min(exchange1(money-1, states), exchange1(money-3, states)), exchange1(money-5, states));
        states[money] = times;
        return times;

    }
}
